`
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
`

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  // 对于整数的不等号等价转换，基于找第一个 >= x
  // 第一个 > x 等价 >= x + 1
  // 最后一个 < x 等价 (>= x) - 1
  // 最后一个 <= x 等价 (> x) - 1
  const start = lower_bound(nums, target)
  if (start === nums.length || nums[start] !== target) {
    return [-1, -1]
  }
  const end = lower_bound(nums, target + 1) - 1
  return [start, end]
};

/**
 * 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
 * 返回最小的满足 nums[i] >= target 的下标
 * 如果不存在，则返回 nums.length
 * @param {number[]} nums 
 * @param {number} target 
 */
function lower_bound(nums, target) {
  // 左闭右闭写法 [left, right]
  let left = 0, right = nums.length - 1
  // 区间里还有元素就继续循环
  while (left <= right) {
    // Math.floor((left + right) / 2)
    // 避免越界
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] < target) {
      left = mid + 1 // [mid + 1, right]
    } else {
      right = mid - 1 // [left, mid - 1]
    }
  }
  return left // left === right + 1
}

function lower_bound2(nums, target) {
  // 左闭右开写法 [left, right)
  let left = 0, right = nums.length
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] < target) {
      left = mid + 1 // [mid + 1, right)
    } else {
      right = mid // [left, mid)
    }
  }
  return left // left === right
}

function lower_bound3(nums, target) {
  // 左开右开写法 (left, right)
  let left = -1, right = nums.length
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] < target) {
      left = mid // (mid, right)
    } else {
      right = mid // (left, mid)
    }
  }
  return right // left + 1 === right
}